package com.leetcode.weicl.problems.no208;

import java.util.HashSet;

/*
 * Problems No 208
 * Implement Trie (Prefix Tree)
 * 
Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

思路：
  一般前导树即可。
  
  可以优化的地方：
   1 由于是小写字母，子节点可以不用遍历，直接定位。
   2 实际的value不需要记忆，只需要记住在此处是否为单词结尾即可。
 */
class TrieNode {
    // Initialize your data structure here.
	char start;
	String value;
	int level = 0;
	
	HashSet<TrieNode> childs = new HashSet<TrieNode>();
	
    public TrieNode() {
        
    }
    public TrieNode(int level, char start) {
        this.level = level;
        this.start = start;
    }
    
    public void insert(String value) {

    	char c = value.charAt(level);
    	boolean finded = false;
    	for (TrieNode node : childs) {
	        if (node.start == c) {

	        	if (level == value.length()-1) {
	        		node.value = value;
	        		return;
	        	}
	        	node.insert(value);
	        	finded = true;
	        }
        }
    	
    	if (!finded) {
    		TrieNode newNode = new TrieNode(level+1, c);
    		if (newNode.level == value.length()) {
    			newNode.value = value;
    		} else {
    			newNode.insert(value);
    		}
    		childs.add(newNode);
    	}
    }
    
    public boolean search(String word) {
    	if (level == word.length()) {
    		return word.equals(value);
    	}
    	char c = word.charAt(level);
    	for (TrieNode node : childs) {
	        if (node.start == c) {
	        	return node.search(word);
	        }
        }
    	
    	return false;
    }
    
    public boolean startsWith(String prefix) {
    	if (level >= prefix.length()) {
    		return true;
    	}
    	char c = prefix.charAt(level);
    	for (TrieNode node : childs) {
	        if (node.start == c) {
	        	return node.startsWith(prefix);
	        }
        }
    	
    	return false;
    }
    
    @Override
    public String toString() {
        return "{" + level +", " + start + ", " + value + "}";
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
    	root.insert(word);
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
    	return root.search(word);
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
    	return root.startsWith(prefix);
    }
    
    public static void main(String[] args) {
    	Trie trie = new Trie();
    	trie.insert("somestring");
    	trie.insert("someone");
    	
    	System.out.println("seach key:" + trie.search("key"));
    	System.out.println("seach someo:" + trie.search("someo"));
    	System.out.println("seach someone:" + trie.search("someone"));
    	System.out.println("seach someonek:" + trie.search("someonek"));
    	
    	System.out.println("startsWith key:" + trie.startsWith("key"));
    	System.out.println("startsWith some:" + trie.startsWith("some"));
    	System.out.println("startsWith someone:" + trie.startsWith("someone"));
    	System.out.println("startsWith someoneb:" + trie.startsWith("someoneb"));
    	
    	trie.insert("abc");
    	testSearch(trie, "abc");
    	
    	trie.insert("ab");
    	testSearch(trie, "ab");
    	
    	trie.insert("ab");
    	testSearch(trie, "ab");
    }
    
    public static void testSearch(Trie trie, String s) {
    	System.out.println("search '"+s+"':" + trie.search(s));
    }
}

// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");
